package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/3 20:13
 *
 丑数：
 1，暴力法，对每个数进行2,3,5除验证。超时
 2，动态规划（三指针）：O(n)
 另dp(n)=为第n个丑数的值，可由上一个丑数*2,*3,*5转移，
 并且使用之后上一个丑数指针应该后移，形成一个最优子结构
 3,最小堆：哈希表+优先队列O(logn)
 由丑数2x,3x,6x组成，每次取出堆顶进行计算，然后放入堆中自动排序。
 同时要注意，不同的计算可能会算出同一个数，因此要进行去重

 有转移倾向和最优子结构的可以考虑动态规划
 有最值，有序特点的可以考虑堆
 */



import java.util.*;

public class Main8 {

    public int GetUglyNumber_Solution(int index) {
        if(index==0)return 0;
        //可能会超出范围，因此使用Long
        //相比于动态规划，dp的第i个数都是前面转移过来的最小值，是先判断在加入
        //而使用堆，是先加入元素后判断，导致新加入的元素超过int
        Set<Long> set=new HashSet<>();
        //默认为小根堆
        PriorityQueue<Long>queue=new PriorityQueue<Long>();

        int factor[]={2,3,5};
        queue.offer(1L);
        set.add(1L);
        Long ans=0L;
        for(int i=0;i<index;++i){
            ans=queue.poll();
            for(int j=0;j<3;++j){
                Long now=factor[j]*ans;
                if(!set.contains(now)){
                    queue.offer(now);
                    set.add(now);
                }
            }
        }
        return ans.intValue();
    }

    /*
    public int GetUglyNumber_Solution(int index) {
        if(index==0)return 0;
        ArrayList<Integer>dp=new ArrayList<>();
        dp.add(1);
        int i=0,j=0,k=0;
        int now=0;
        while (now<index){
            int num=Math.min(Math.min(dp.get(i)*2,dp.get(j)*3),dp.get(k)*5);
            dp.add(num);
            now++;
            //必须分开判断，因为可能由2种情况转移到了同一个值
            if(num==dp.get(i)*2)i++;
            if(num==dp.get(j)*3)j++;
            if(num==dp.get(k)*5)k++;
        }
        return dp.get(index-1);
    }
    */

    /*
    public boolean check(int n){
        while(n%2==0){
            n>>=1;
        }
        while(n%3==0){
            n/=3;
        }
        while(n%5==0){
            n/=5;
        }
        //System.out.println(n);
        return n==1;
    }

    public int GetUglyNumber_Solution(int index) {
        int res=0;
        for(int i=1;i<=Integer.MAX_VALUE;++i){
            if(check(i)){
                index--;
                res=i;
            }
            if(index==0)break;
        }
        return res;
    }
*/


}
